APPROXIMATION ALGORITHMS AND PREUDOMETRIC VARIANT OF A TRAVELLING SALESMAN PROBLEM

Borisova Elena Sergeevna, Post graduate student, Togliatti State University, e-lena-borisova@mail.ru
Melnikov Boris Felixovich, Doctor of physico-mathematical sciences, professor, sub-department of applied mathematics and applied computer science, Togliatti State University, B.Melnikov@tltsu.ru

004.021:519.8:519.724.6

An Article contains classical approach to approximation algorithms, there are given examples illustrating the basic definition of these algorithms. There are contained polynomial-time approximation scheme and fully polynomial-time approximation scheme. There is cited an example psevdometric traveling salesperson problem. Efficient algorithms giving optimal solution this problem haven’t yet developed.

approximation algorithms, relative error, approximation ratio, approximation scheme, psevdometric traveling salesperson problem.